We study the following two functions: d(n,c) and $\vec{d}(n,c)$; d(n,c)($\vec{d}(n,c)$) is the minimum number k such that every c-edge-coloredundirected (directed) graph of order n and minimum monochromatic degree(out-degree) at least k has a properly colored cycle. Abouelaoualim et al.(2007) stated a conjecture which implies that d(n,c)=1. Using a recursiveconstruction of c-edge-colored graphs with minimum monochromatic degree p andwithout properly colored cycles, we show that $d(n,c)\ge {1 \over c}(\log_cn-\log_c\log_cn)$ and, thus, the conjecture does not hold. In particular, thisinequality significantly improves a lower bound on $\vec{d}(n,2)$ obtained byGutin, Sudakov and Yeo in 1998.
展开▼
